package com.zjsru.studyplan1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 合并二叉树
 * <p>
 * 输入:
 * Tree 1                     Tree 2
 *     1                         2
 *    / \                       / \
 *   3   2                     1   3
 *  /                           \   \
 * 5                             4   7
 * 输出:
 * 合并后的树:
 * 3
 * / \
 * 4   5
 * / \   \
 * 5   4   7
 * <p>
 * <p>
 * 深度优先搜索
 * 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
 * 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
 * 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class mergeTrees {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode newTrees = new TreeNode(root1.val + root2.val);
        newTrees.left = mergeTrees(root1.left, root2.left);
        newTrees.right = mergeTrees(root1.right, root2.right);
        return newTrees;
    }
    //广度优先搜索
//    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
//        if (t1 == null) {
//            return t2;
//        }
//        if (t2 == null) {
//            return t1;
//        }
//        TreeNode merged = new TreeNode(t1.val + t2.val);
//        Queue<TreeNode> queue = new LinkedList<TreeNode>();
//        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
//        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
//        queue.offer(merged);
//        queue1.offer(t1);
//        queue2.offer(t2);
//        while (!queue1.isEmpty() && !queue2.isEmpty()) {
//            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
//            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
//            if (left1 != null || left2 != null) {
//                if (left1 != null && left2 != null) {
//                    TreeNode left = new TreeNode(left1.val + left2.val);
//                    node.left = left;
//                    queue.offer(left);
//                    queue1.offer(left1);
//                    queue2.offer(left2);
//                } else if (left1 != null) {
//                    node.left = left1;
//                } else if (left2 != null) {
//                    node.left = left2;
//                }
//            }
//            if (right1 != null || right2 != null) {
//                if (right1 != null && right2 != null) {
//                    TreeNode right = new TreeNode(right1.val + right2.val);
//                    node.right = right;
//                    queue.offer(right);
//                    queue1.offer(right1);
//                    queue2.offer(right2);
//                } else if (right1 != null) {
//                    node.right = right1;
//                } else {
//                    node.right = right2;
//                }
//            }
//        }
//        return merged;
//    }
}
